#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

 // Definition for singly-linked list.
  struct ListNode
  {
     int val;
      struct ListNode *next;
  };
 


struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* head_1, * tail_1, * head_2, * tail_2;
    head_1 = tail_1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail_1->next = NULL;
    head_2 = tail_2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail_2->next = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val < x)
        {
            tail_1->next = cur;
            tail_1 = cur;
        }
        else
        {
            tail_2->next = cur;
            tail_2 = cur;
        }
        cur = cur->next;
    }
    tail_2->next = NULL;
    tail_1->next = head_2->next;
    struct ListNode* newhead = head_1->next;
    free(head_1);
    free(head_2);
    return newhead;
}
int main()
{
    return 0;
}